package com.tys.algorithm.advanced.code.class12;

// 在线测试链接 : https://leetcode.com/problems/largest-bst-subtree
public class Code05_MaxSubBSTSize {

    // 提交时不要提交这个类
    public static class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;

        public TreeNode(int value) {
            val = value;
        }
    }

    // 提交如下的代码，可以直接通过
    public static int largestBSTSubtree(TreeNode head) {
        if (head == null) {
            return 0;
        }
        return process(head).maxBSTSubtreeSize;
    }

    public static class Info {
        public int maxBSTSubtreeSize; //最大的满足搜索二叉子树的大小
        public int allSize; //整棵树的大小
        public int max; //最大值
        public int min; //最小值

        public Info(int m, int a, int ma, int mi) {
            maxBSTSubtreeSize = m;
            allSize = a;
            max = ma;
            min = mi;
        }
    }

    public static Info process(TreeNode x) {
        if (x == null) {  //空树返回null，不知道设置啥
            return null;
        }
        //左树信息
        Info leftInfo = process(x.left);
        //右树信息
        Info rightInfo = process(x.right);
        //最大值
        int max = x.val; //当前节点值
        int min = x.val; //当前节点值
        int allSize = 1; //当前节点
        //左树不为null
        if (leftInfo != null) {
            //最大值
            max = Math.max(leftInfo.max, max);
            //最小值
            min = Math.min(leftInfo.min, min);
            //左树大小累加到整棵树大小
            allSize += leftInfo.allSize;
        }
        //右树不为null
        if (rightInfo != null) {
            //最大值
            max = Math.max(rightInfo.max, max);
            //最小值
            min = Math.min(rightInfo.min, min);
            //右树大小累加到整棵树大小
            allSize += rightInfo.allSize;
        }
        //情况1：左树
        int p1 = -1; //最后比max,这里设置为-1
        if (leftInfo != null) {
            //左树满足最大二叉搜索子树的大小
            p1 = leftInfo.maxBSTSubtreeSize;
        }
        //情况2：右树
        int p2 = -1; //最后比max,这里设置为-1
        if (rightInfo != null) {
            //右树满足最大二叉搜索子树的大小
            p2 = rightInfo.maxBSTSubtreeSize;
        }
        //情况3：
        int p3 = -1;  //最后比max,这里设置为-1
        //认为左树是搜索二叉树
        //1 左树为null
        //2 左树不为null：最大搜索二叉树的大小和整棵树大小相等
        boolean leftBST = leftInfo == null ? true : (leftInfo.maxBSTSubtreeSize == leftInfo.allSize);
        //认为右树是搜索二叉树:
        //1 右树为null
        //2 右树不为null：最大搜索二叉树的大小和整棵树大小相等
        boolean rightBST = rightInfo == null ? true : (rightInfo.maxBSTSubtreeSize == rightInfo.allSize);
        //左树和右树都是搜索二叉树
        if (leftBST && rightBST) {
            //左树最大值小于X：为null满足
            boolean leftMaxLessX = leftInfo == null ? true : (leftInfo.max < x.val);
            //右树最小值大于X：为null满足
            boolean rightMinMoreX = rightInfo == null ? true : (x.val < rightInfo.min);
            //满足搜索二叉树
            if (leftMaxLessX && rightMinMoreX) {
                //左树大小
                int leftSize = leftInfo == null ? 0 : leftInfo.allSize;
                //右树大小
                int rightSize = rightInfo == null ? 0 : rightInfo.allSize;
                //整颗树的大小
                p3 = leftSize + rightSize + 1;
            }
        }
        //三种情况取最大
        return new Info(Math.max(p1, Math.max(p2, p3)), allSize, max, min);
    }

}
